package com.itheima.leetcode.od.b.graph;

import java.util.*;

/**
 * <h3>连连看游戏</h3>
 * 小明在玩连连看游戏，目标是消除相同的数字，游戏规定：
 * <p>
 * 1. 两个位置必须数字相同才能消除
 * <p>
 * 2. 连接路径只能经过空格
 * <p>
 * 3. 连接路径最多只能有两次拐弯
 * <p>
 * 4. 连接线路可以走地图的边界
 * <p>
 * 5. 消除后位置变为空格("")
 * <p>
 * 输入描述：
 * <p>
 * 第一行输入一个字符串，代表连连看的地图矩阵，形式类似于: [[4,5,4],[5,4,5]]
 * 第二行输入n，表示操作步骤数
 * 接下来n行，每行输入四个数字 y1 x1 y2 x2 代表此次操作的两个位置
 * <p>
 * 输出描述：
 * <p>
 * 输入步骤能全部正常消除则输出 OK，否则输出 NO
 * <p>
 * 备注：
 * 不必考虑输入不合法的情况
 * <p>
 * 示例1：
 * <p>
 * 输入：
 * <p>
 * [[4,5,4],[5,4,5]]
 * <p>
 * 2
 * <p>
 * 0 0 2 0
 * <p>
 * 1 0 0 1
 * <p>
 * 输出：
 * OK
 * <p>
 * 说明：
 * <p>
 * 位置（0，0）到位置（0，2）上，都是4，可以消除
 * <p>
 * 位置（0，1）到位置（1，0）上，都是5，可以消除
 */
public class DFSProcessGameMap {
    public static void main(String[] args) {
        /*Scanner scanner = new Scanner(System.in);
        String inputStr = scanner.nextLine();
        int operationCount = Integer.parseInt(scanner.nextLine());

        String[][] gameBoard = getResult(inputStr);

        for (int i = 0; i < operationCount; i++) {
            String[] coords = scanner.nextLine().split(" ");
            int y1 = Integer.parseInt(coords[0]) + 1;
            int x1 = Integer.parseInt(coords[1]) + 1;
            int y2 = Integer.parseInt(coords[2]) + 1;
            int x2 = Integer.parseInt(coords[3]) + 1;

            if (!verifyConnection(gameBoard, x1, y1, x2, y2)) {
                System.out.println("NO");
                return;
            }
        }

        System.out.println("OK");*/

        String inputStr = "[[4,5,4],[5,4,5]]";
        int operationCount = 2;

        String[][] gameBoard = processGameMap(inputStr);

        int[][] coords = Arrays.stream("0 0 2 0\n1 0 0 1\n".split("\n"))
                .map(s -> Arrays.stream(s.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        System.out.println(getResult(coords, gameBoard));
    }

    // 元素含义【行偏移，列偏移，运动方向】，运动方向：1上，2下，3左，4右
    private static int[][] offsets = {{-1, 0, 1}, {1, 0, 2}, {0, -1, 3}, {0, 1, 4}};

    private static String getResult(int[][] coords, String[][] gameBoard) {

        boolean result = true;
        for (int[] coord : coords) {
            int y1 = coord[0] + 1;
            int x1 = coord[1] + 1;
            int y2 = coord[2] + 1;
            int x2 = coord[3] + 1;

            if (!verifyConnection(gameBoard, x1, y1, x2, y2)) {
                result = false;
                break;
            }
        }

        return result ? "OK" : "NO";
    }

    /**
     * 生成地图字符串矩阵
     *
     * @param inputStr
     * @return
     */
    private static String[][] processGameMap(String inputStr) {

        inputStr = inputStr.substring(1, inputStr.length() - 1);
        String[][] matrix = Arrays.stream(inputStr.split("(?<=]),(?=\\[)"))
                .map(string -> string.substring(1, string.length() - 1)
                        .split(","))
                .toArray(String[][]::new);

        // 获取尺寸
        int originalRows = matrix.length;
        int originalCols = matrix[0].length;

        // 创建带边界的地图
        String[][] gameMap = new String[originalRows + 2][originalCols + 2];
        for (String[] row : gameMap) {
            Arrays.fill(row, " ");
        }

        // 填充数据
        for (int i = 0; i < matrix.length; i++) {
            String[] cells = matrix[i];
            System.arraycopy(cells, 0, gameMap[i + 1], 1, cells.length);
        }

        return gameMap;
    }

    /**
     * 检查连接
     *
     * @param board
     * @param x1
     * @param y1
     * @param x2
     * @param y2
     * @return
     */
    private static boolean verifyConnection(String[][] board, int x1, int y1, int x2, int y2) {
        if (!board[x1][y1].equals(board[x2][y2])) {
            return false;
        }
        if (x1 == x2 && y1 == y2) {
            return false;
        }

        Set<Integer> visited = new HashSet<>();
        visited.add(x1 * board[0].length + y1); // 二位坐标一维化

        if (explorePath(board, x1, y1, x2, y2, -1, 0, visited)) {
            board[x1][y1] = " ";
            board[x2][y2] = " ";
            return true;
        }
        return false;
    }

    /**
     * DFS搜索路径（一维坐标）
     *
     * @param board
     * @param currX
     * @param currY
     * @param targetX
     * @param targetY
     * @param currDir
     * @param turns
     * @param visited
     * @return
     */
    private static boolean explorePath(String[][] board,
                                       int currX, int currY,
                                       int targetX, int targetY,
                                       int currDir, int turns,
                                       Set<Integer> visited) {
        int rowCnt = board.length;
        int colCnt = board[0].length;

        // 到达目标
        if (currX == targetX && currY == targetY) {
            return true;
        }

        for (int[] offset : offsets) {
            int nextDir = offset[2];
            int nextX = currX + offset[0];
            int nextY = currY + offset[1];

            // 边界检查
            if (nextX < 0 || nextX >= rowCnt || nextY < 0 || nextY >= colCnt) {
                continue;
            }

            // 访问检查
            if (visited.contains(nextX * colCnt + nextY)) {
                continue;
            }

            // 路径检查（连接路径只能经过空格）
            if (!(nextX == targetX && nextY == targetY) && !board[nextX][nextY].equals(" ")) {
                continue;
            }

            // 计算拐弯
            int nextTurns = turns + (currDir != -1 && currDir != nextDir ? 1 : 0);

            // 如果拐弯次数用完了，则不走
            if (nextTurns > 2) {
                continue;
            }

            // 记录访问
            visited.add(nextX * colCnt + nextY);

            if (explorePath(board, nextX, nextY, targetX, targetY, nextDir, nextTurns, visited)) {
                return true;
            }

            visited.remove(nextX * colCnt + nextY);
        }

        return false;
    }
}